package com.suanfa.search;

public class BinarySearch {

/*
    param :  a  -待查找的升序数组
             target -目标值
    Returns:
            找到返回索引
            找不到返回-1
    时间复杂度：最坏0(logn)，最好O(1)
    空间复杂度：O(1)

    改进二分查找，解决查找次数不平衡问题
    java内置Array.utill.binary 前面相同，返回值是升序插入的索引
    真正插入要拷贝数组
*/

    public static int binarySearchBasic(int[] a, int target){
        int i =0,j=a.length-1; //设置指针和初值
        while(i<=j){     //为什么有=
            int m = (i+j)/2;   //如果数组的长度为Interger.MAX_VALUE
            if(target<a[m]){      //java把最高位看成是符号位  改成符号右1运算  >>>1
                j = m-1;
            } else if (a[m] < target) {
                i =m +1;
            }else{
                return m;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] a = {7,13,21,30,38,44,52,53};
        System.out.println(binarySearchBasic(a, 7) == 0);
        System.out.println(binarySearchBasic(a, 13) == 7);
        System.out.println(binarySearchBasic(a, 21) == 2);
        System.out.println(binarySearchBasic(a, 30) == 3);
        System.out.println(binarySearchBasic(a, 0) == -1);
        System.out.println(binarySearchBasic(a, 15) == -1);
    }
}
